package net.tp.algo.graph;

import java.util.*;
import net.tp.struct.adt.*;

/**
 *
 * @author Trung Phan
 */
public class EulerGraph {


    /**
     *
     * @param graph undirected graph
     * @param source source node
     * @return Euler cycle
     */
    public static List<Integer> findEulerCycle(Graph graph, int source) {

        int N = graph.order();

        // build our own collection of edges so that we can remove the edges later
        @SuppressWarnings({"unchecked", "rawtypes"})
        Set<Graph.Edge>[] edges = new Set[N];
        for (int i = 0; i < N; i++) {
            edges[i] = new HashSet<>();
        }

        for (int u = 0; u < N; u++) {
            if (graph.degree(u) % 2 != 0) {
                throw new IllegalArgumentException("This is not Euler graph.");
            }
            for (Graph.Edge edge : graph.edges(u)) {
                int w = edge.other(u);
                edges[u].add(edge);
                edges[w].add(edge);
            }
        }

        SinglyNode<Integer> head = new SinglyNode<>(source, null);
        SinglyNode<Integer> activeSinglyNode = head;
        Set<SinglyNode<Integer>> unsaturatedSinglyNodes = new HashSet<>();

        while (true) {

            int u = activeSinglyNode.element;
            if (edges[u].size() > 0) {

                Graph.Edge edge = edges[u].iterator().next();
                int w = edge.other(u);

                edges[u].remove(edge);
                edges[w].remove(edge);

                if (!edges[u].isEmpty()) {
                    unsaturatedSinglyNodes.add(activeSinglyNode);
                }

                activeSinglyNode = activeSinglyNode.next = new SinglyNode<>(w, activeSinglyNode.next);
            }
            else if (unsaturatedSinglyNodes.isEmpty()) {
                break;
            }
            else {
                activeSinglyNode = unsaturatedSinglyNodes.iterator().next();
                unsaturatedSinglyNodes.remove(activeSinglyNode);
            }
        }

        List<Integer> result = new ArrayList<>();
        for (; head != null; head = head.next) {
            result.add(head.element);
        }

        return result;
    }

}
